package com.gjx.leetcode;

//138. 复制带随机指针的链表
//给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
//
//要求返回这个链表的深拷贝。 
//
// 
//
//示例：
//
//
//
//输入：
//{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}
//
//解释：
//节点 1 的值是 1，它的下一个指针和随机指针都指向节点 2 。
//节点 2 的值是 2，它的下一个指针指向 null，随机指针指向它自己。
// 
//
//提示：
//
//你必须返回给定头的拷贝作为对克隆列表的引用。

public class Solution138 {
	public Node copyRandomList(Node head) {
		if (head == null) {
			return null;
		}
		
		extend(head);
		updateRandom(head);
		return split(head);
		
	}
	
	private void extend(Node head) {
		
		while (head != null) {
			
			Node node = new Node(head.val, head.next, null);
			
			head.next = node;
			
			head = node.next;
			
		}
		
	}
	
	private void updateRandom(Node head) {
		
		while (head != null) {
			if (head.random != null) {
				head.next.random = head.random.next;
			}
			head = head.next.next;
			
		}
		
	}
	
	private Node split(Node head) {
		
		Node newHead = head.next;
		
		while (head != null) {
			
			Node copy = head.next;
			
			head.next = copy.next;
			
			head = head.next;
			
			if (head != null) {
				copy.next = head.next;
			}
			
		}
		
		return newHead;
	}
	
}
